package com.leetcode.sort.basic_sort;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;

/**
 * @author Dennis Li
 * @date 2020/9/9 23:09
 */
public class MergeSort extends Sort {

    public static void sort(int[] nums, int lo, int hi, int[] aux) {
        if (lo >= hi) return;

        int mid = lo + (hi - lo) / 2;
        sort(nums, lo, mid, aux);
        sort(nums, mid + 1, hi, aux);

        merge(nums, lo, mid, hi, aux);
    }

    private static void merge(int[] nums, int lo, int mid, int hi, int[] aux) {
        int i = lo, j = mid + 1;

        System.arraycopy(nums, lo, aux, lo, hi - lo + 1);

        for (int k = lo; k <= hi; k++) {
            if (i > mid)
                nums[k] = aux[j++];
            else if (j > hi)
                nums[k] = aux[i++];
            else if (aux[i] <= aux[j])
                nums[k] = aux[i++];
            else
                nums[k] = aux[j++];
        }
    }

    static class Practice extends Sort {

        public static void main(String[] args) {
            long start = System.currentTimeMillis();
            for (int i = 0; i < 10; i++) {
                int[] nums = generateArray(100000);
                sort(nums, 0, nums.length - 1, new int[nums.length]);
                System.out.println(isSorted(nums));
            }
            System.out.println(System.currentTimeMillis() - start);
        }

        public static void sort(int[] nums, int lo, int hi, int[] aux) {
            if (lo >= hi) {
                return;
            }
            int mid = lo + (hi - lo) / 2;
            sort(nums, lo, mid, aux);
            sort(nums, mid + 1, hi, aux);

            merge(nums, lo, mid, hi, aux);
        }

        private static void merge(int[] nums, int lo, int mid, int hi, int[] aux) {
            int i = lo, j = mid + 1;

            System.arraycopy(nums, lo, aux, lo, hi - lo + 1);

            for (int k = lo; k <= hi; k++) {
                if (i > mid)
                    nums[k] = aux[j++];
                else if (j > hi)
                    nums[k] = aux[i++];
                else if (aux[i] <= aux[j])
                    nums[k] = aux[i++];
                else
                    nums[k] = aux[j++];
            }
        }
    }

}
